package com.mj.Tree;

import com.mj.printer.BinaryTreeInfo;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: LDeng
 * @Date: 2021-03-03 11:31
 */
public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;//根节点属性


    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root=null;
        size=0;
    }

    //节点类
    protected static class Node<E> {
        E element;//节点存储的元素
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {//构造
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChind(){
            return parent!=null && this==parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this==parent.right;
        }

        public Node<E> sibling(){
            if(isLeftChind()){
                return parent.right;
            }
            if(isRightChild()){
                return parent.left;
            }
            //没有左也没有右，父节点为空， 返回空兄弟节点
            return null;
        }

    }

    //前序遍历二叉树（根->左->右）
    public void preorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        preorderTraversal(root, visitor);
    }

    //前序遍历二叉树
    public void preorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorderTraversal(node.left, visitor);
        preorderTraversal(node.right, visitor);
    }

    //中序遍历(左->根->右)
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    public void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;
        inorderTraversal(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);
    }

    //后序遍历(左->右->根)
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(root, visitor);
    }

    public void postorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;//递归终止判断
        postorderTraversal(node.left, visitor);
        postorderTraversal(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);

    }

    //层序遍历
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);//根节点入队
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();//头节点出队
            if (visitor.visit(node.element)) return;//将元素传出去， 并获取返回值（boolean）， true 就不在入队循环
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }


    //计算二叉树高度（递归）
    public int height() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    //计算二叉树高度（迭代）,层序遍历
    public int height1() {
        if (root == null) return 0;
        int height = 0;//树的高度
        int levelSize = 1;//每一层的元素个数
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;//本层元素数量--
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelSize == 0) {//levelSize=0 意味着本层已经全部出栈， 准备访问下一层
                //下一层元素数量是队列的size;
                levelSize = queue.size();
                height++;
            }
        }
        return height;
    }

    protected Node<E> createNode(E element, Node<E> parent){
        return new Node<>(element,parent);
    }

    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;//要的是叶子节点，给的不是
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {//左边空， 右边不空
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {//右边为空， 需要判断剩下的所有节点必须都是叶子节点
                leaf = true;
            }
        }
        return true;
    }



    //前驱节点， 中序遍历时的前一个节点（左子树的最后一个节点）
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        //1 ，左边不为空，前驱节点在左子树中(left.right.right.....)
        Node<E> p = node.left;
        if (p != null) {
            p = node.left;
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        //从父节点，祖父节点。。。中寻找前驱节点,
        // 父节点不为空， 并且本节点在父节点的左子树中
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        //node.parent==null ==>返回空（node.parent）
        //node==node.parent.right ==> 本节点的parent节点就是前驱
        return node.parent;
    }

    //后续节点， 中序遍历时的前一个节点（左子树的最后一个节点）
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;
        //1 ，右边不为空，前驱节点在右子树中(right.left.left.....)
        Node<E> p = node.right;
        if (p != null) {
            p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        //从父节点，祖父节点。。。中寻找前驱节点,
        // 父节点不为空， 并且本节点在父节点的左子树中
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        //node.parent==null ==>返回空（node.parent）
        //node==node.parent.right ==> 本节点的parent节点就是前驱
        return node.parent;
    }




    public static abstract class Visitor<E> {
        boolean stop;

        //如果返回true, 就停止遍历
        abstract boolean visit(E element);
    }


    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return node;
    }

}
